<html>
 <head>
  <meta charset="UTF-8">
 </head>
 <body>
  <h1 data-lake-id="cE6vK" id="cE6vK"><span data-lake-id="udac3a403" id="udac3a403">典型回答</span></h1>
  <p data-lake-id="u0e25bebf" id="u0e25bebf"><span data-lake-id="u3dc28291" id="u3dc28291">对于JDK1.8来说，如果用一句话来讲的话，ConcurrentHashMap是通过synchronized和CAS自旋保证的线程安全，要想知道ConcurrentHashMap是如何加锁的，就要知道HashMap在哪些地方会导致线程安全问题，如初始化桶数组阶段和设置桶，插入链表，树化等阶段，都会有并发问题。</span></p>
  <p data-lake-id="u2aaa1d3a" id="u2aaa1d3a"><span data-lake-id="uf5ce53f3" id="uf5ce53f3">​</span><br></p>
  <p data-lake-id="ud2f940b8" id="ud2f940b8"><span data-lake-id="u72f7bce0" id="u72f7bce0">解决这些问题的前提，就要知道到底有多少线程在对map进行写入操作，这里ConcurrentHashMap通过sizeCtl变量完成，如果其为负数，则说明有多线程在操作，且Math.abs(sizeCtl)即为线程的数目。</span></p>
  <h2 data-lake-id="CtYXY" id="CtYXY"><span data-lake-id="u4fbd0725" id="u4fbd0725">初始化桶阶段</span></h2>
  <p data-lake-id="u72cec7ee" id="u72cec7ee"><br></p>
  <p data-lake-id="u5752cd95" id="u5752cd95"><span data-lake-id="u3068b007" id="u3068b007">如果在此阶段不做并发控制，那么极有可能出现多个线程都去初始化桶的问题，导致内存浪费。所以Map在此处采用自旋操作和CAS操作，如果此时没有线程初始化，则去初始化，否则当前线程让出CPU时间片，等待下一次唤醒，源码如下：</span></p>
  <pre lang="java"><code>
while ((tab = table) == null || tab.length == 0) {
    if ((sc = sizeCtl) &lt; 0)
        Thread.yield(); // lost initialization race; just spin
    else if (U.compareAndSetInt(this, SIZECTL, sc, -1)) {
        try {
            if ((tab = table) == null || tab.length == 0) {
                // 省略
            }
        } finally {
            sizeCtl = sc;
        }
        break;
    }
}
</code></pre>
  <h2 data-lake-id="WBmlV" id="WBmlV"><br></h2>
  <h2 data-lake-id="KAbZV" id="KAbZV"><span data-lake-id="u9165c1b5" id="u9165c1b5">put元素阶段</span></h2>
  <p data-lake-id="u93fd4fdd" id="u93fd4fdd"><span data-lake-id="u219f3773" id="u219f3773">如果hash后发现桶中没有值，则会直接采用CAS插入并且返回</span></p>
  <p data-lake-id="uf557cb5b" id="uf557cb5b"><span data-lake-id="uc5ecf65d" id="uc5ecf65d">如果发现桶中有值，则对流程按照当前的桶节点为维度进行加锁，将值插入链表或者红黑树中，源码如下：</span></p>
  <pre lang="java"><code>
// 省略....
// 如果当前桶节点为null，直接CAS插入
else if ((f = tabAt(tab, i = (n - 1) &amp; hash)) == null) {
    if (casTabAt(tab, i, null, new Node&lt;K,V&gt;(hash, key, value)))
        break;                   // no lock when adding to empty bin
}
// 省略....
// 如果桶节点不为空，则对当前桶进行加锁
else {
    V oldVal = null;
    synchronized (f) {
    }
}
                
</code></pre>
  <h2 data-lake-id="WGtJb" id="WGtJb"><br></h2>
  <h2 data-lake-id="WWVZI" id="WWVZI"><span data-lake-id="u51ff4a8f" id="u51ff4a8f">扩容阶段</span></h2>
  <p data-lake-id="u35cbea19" id="u35cbea19"><span data-lake-id="uc12cf866" id="uc12cf866">多线程最大的好处就是可以充分利用CPU的核数，带来更高的性能，所以ConcurrentHashMap并没有一味的通过CAS或者锁去限制多线程，在扩容阶段，ConcurrentHashMap就通过多线程来加加速扩容。</span></p>
  <p data-lake-id="uf5ca3ba2" id="uf5ca3ba2"><span data-lake-id="u38571040" id="u38571040">在分析之前，我们需要知道两件事情：</span></p>
  <p data-lake-id="u84bb65e9" id="u84bb65e9"><span data-lake-id="uf741bed6" id="uf741bed6">​</span><br></p>
  <ol list="ucbbf385d">
   <li fid="u000ea76f" data-lake-id="u2f155af3" id="u2f155af3"><span data-lake-id="u3a9d6ea4" id="u3a9d6ea4">ConcurrentHashMap通过ForwardingNode来记录当前已经桶是否被迁移，如果</span><code data-lake-id="u17ced368" id="u17ced368"><span data-lake-id="u612d3f49" id="u612d3f49">oldTable[i] instanceOf ForwardingNode</span></code><span data-lake-id="u0430b87e" id="u0430b87e">则说明处于i节点的桶已经被移动到newTable中了。它里面有一个变量nextTable，指向的是下一次扩容后的table</span></li>
   <li fid="u000ea76f" data-lake-id="uc4b3321e" id="uc4b3321e"><span data-lake-id="u8be5c5ae" id="u8be5c5ae">transferIndex记录了当前扩容的桶索引，最开始为oldTable.length，它给下一个线程指定了要扩容的节点</span></li>
  </ol>
  <p data-lake-id="u25a7594f" id="u25a7594f"><span data-lake-id="ue9b8bfba" id="ue9b8bfba">得知到这两点后，我们可以梳理出如下扩容流程：</span></p>
  <ol list="uc607bba6">
   <li fid="u9f4087da" data-lake-id="u781bf890" id="u781bf890"><span data-lake-id="uc195e40e" id="uc195e40e">通过CPU核数为每个线程计算划分任务，每个线程最少的任务是迁移16个桶</span></li>
   <li fid="u9f4087da" data-lake-id="u157ee332" id="u157ee332"><span data-lake-id="u5e116126" id="u5e116126">将当前桶扩容的索引transferIndex赋值给当前线程，如果索引小于0，则说明扩容完毕，结束流程，否则</span></li>
   <li fid="u9f4087da" data-lake-id="uc5512db8" id="uc5512db8"><span data-lake-id="u296bce69" id="u296bce69">再将当前线程扩容后的索引赋值给transferIndex，譬如，如果transferIndex原来是32，那么赋值之后transferIndex应该变为16，这样下一个线程就可以从16开始扩容了。这里有一个小问题，如果两个线程同时拿到同一段范围之后，该怎么处理？答案是ConcurrentHashMap会通过CAS对transferIndex进行设置，只可能有一个成功，所以就不会存在上面的问题</span></li>
   <li fid="u9f4087da" data-lake-id="uadbf0bf6" id="uadbf0bf6"><span data-lake-id="ude1d30a6" id="ude1d30a6">之后就可以对真正的扩容流程进行加锁操作了</span></li>
  </ol>
  <p data-lake-id="u008cef11" id="u008cef11"><br></p>
  <h1 data-lake-id="QEko2" id="QEko2"><span data-lake-id="u26e5f1cb" id="u26e5f1cb">知识扩展</span></h1>
  <h2 data-lake-id="VwMnG" id="VwMnG"><strong><span data-lake-id="u2d114b0f" id="u2d114b0f" class="lake-fontsize-24" style="color: rgb(38, 38, 38)">ConcurrentSkipListMap和ConcurrentHashMap有什么区别</span></strong></h2>
  <p data-lake-id="u03db0da4" id="u03db0da4"><span data-lake-id="ufe477c4e" id="ufe477c4e">ConcurrentSkipListMap是一个内部使用跳表，并且支持排序和并发的一个Map，是线程安全的。一般很少会被用到，也是一个比较偏门的数据结构。</span></p>
  <p data-lake-id="u61191ae2" id="u61191ae2"><span data-lake-id="u7309d396" id="u7309d396">​</span><br></p>
  <p data-lake-id="u17149458" id="u17149458"><span data-lake-id="u69b53095" id="u69b53095">简单介绍下跳表（跳表是一种允许在一个有顺序的序列中进行快速查询的数据结构。在普通的顺序链表中查询一个元素，需要从链表头部开始一个一个节点进行遍历，然后找到节点。如图1。跳表可以解决这种查询时间过长，其元素遍历的图示如图2，跳表是一种使用”空间换时间”的概念用来提高查询效率的链表。）；</span></p>
  <p data-lake-id="uf9863452" id="uf9863452"><span data-lake-id="u1c32a144" id="u1c32a144">​</span><br></p>
  <p data-lake-id="uaa511730" id="uaa511730"><span data-lake-id="ub887ae02" id="ub887ae02">ConcurrentSkipListMap 和 ConcurrentHashMap 的主要区别：</span></p>
  <ol list="u34fe2e1a">
   <li fid="u3feb5d69" data-lake-id="u1dfcc4df" id="u1dfcc4df"><span data-lake-id="ua14f73e0" id="ua14f73e0">底层实现方式不同。C</span><strong><span data-lake-id="uee739aa6" id="uee739aa6">oncurrentSkipListMap底层基于跳表。ConcurrentHashMap底层基于Hash桶和红黑树</span></strong></li>
   <li fid="u3feb5d69" data-lake-id="u84b14d32" id="u84b14d32"><strong><span data-lake-id="ub1a47f1e" id="ub1a47f1e">ConcurrentHashMap不支持排序。ConcurrentSkipListMap支持排序。</span></strong></li>
  </ol>
  <p data-lake-id="uc4dbb1bd" id="uc4dbb1bd"><img src="https://cdn.nlark.com/yuque/0/2022/jpeg/5378072/1665119055515-c5701dc8-ac99-4a28-929e-20b8a38280be.jpeg?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_20%2Ctext_SmF2YeWFq-iCoQ%3D%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10%2Fresize%2Cw_714%2Climit_0%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_20%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <h2 data-lake-id="S0pNy" id="S0pNy"><br></h2>
  <h2 data-lake-id="BOwFo" id="BOwFo"><span data-lake-id="u41898d27" id="u41898d27" style="color: rgb(38, 38, 38)">SynchronizedList和Vector的区别</span></h2>
  <p data-lake-id="uf61dce4b" id="uf61dce4b"><span data-lake-id="u18631be5" id="u18631be5">Vector是java.util包中的一个类。 SynchronizedList是java.util.Collections中的一个静态内部类。</span></p>
  <p data-lake-id="u1c75832d" id="u1c75832d"><span data-lake-id="u11111689" id="u11111689">在多线程的场景中可以直接使用Vector类，也可以使用Collections.synchronizedList(List list)方法来返回一个线程安全的List。</span></p>
  <p data-lake-id="u0647075a" id="u0647075a"><span data-lake-id="u92a33967" id="u92a33967">1.如果使用add方法，那么他们的扩容机制不一样。 </span></p>
  <p data-lake-id="ua8894860" id="ua8894860"><span data-lake-id="u3e38eb7a" id="u3e38eb7a">2.SynchronizedList可以指定锁定的对象。即锁粒度是同步代码块。而Vector的锁粒度是同步方法。</span></p>
  <p data-lake-id="ucc738094" id="ucc738094"><span data-lake-id="u81fd4a9a" id="u81fd4a9a">3.SynchronizedList有很好的扩展和兼容功能。他可以将所有的List的子类转成线程安全的类。 </span></p>
  <p data-lake-id="u476b6eee" id="u476b6eee"><span data-lake-id="u7edfc47c" id="u7edfc47c">4.使用SynchronizedList的时候，进行遍历时要手动进行同步处理。</span></p>
  <p data-lake-id="u55738641" id="u55738641"><span data-lake-id="u95a33cce" id="u95a33cce">5.SynchronizedList可以指定锁定的对象。</span></p>
  <p data-lake-id="u8e79006c" id="u8e79006c"><span data-lake-id="ud66ade51" id="ud66ade51">更多内容参见我的详细文章介绍：http://www.hollischuang.com/archives/498</span></p>
 </body>
</html>